package com.yeung.swordoffer;

import java.util.ArrayList;
import java.util.Comparator;

/**
 * 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
 * 输出描述:
 * 对应每个测试案例，输出两个数，小的先输出。
 */
public class 和为S的两个数字 {
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        ArrayList<Tuple2> tmp = new ArrayList<>();
        for (int i = 0; i < array.length; i++)
            for (int k = i; k < array.length; k++) {
                if (array[i] + array[k] == sum)
                    tmp.add(new Tuple2(array[i], array[k]));
            }
        tmp.sort(new Comparator<Tuple2>() {
            @Override
            public int compare(Tuple2 o1, Tuple2 o2) {
                return o1.get_1() * o1.get_2() - o2.get_1() * o2.get_2();
            }
        });
        if (tmp.size() < 1) return new ArrayList<Integer>();
        Tuple2 tuple2 = tmp.get(0);
        tuple2.sort();
        ArrayList<Integer> list = new ArrayList<>();
        list.add(tuple2.get_1());
        list.add(tuple2.get_2());
        return list;
    }


}
